#ifndef __BWLIB_STRING_KMP_H__
#define __BWLIB_STRING_KMP_H__
#include "../config.h"
#include <cstring>
#include <stdexcept>

namespace bwlib
{
	/* @brief: 计算 KMP 算法的失配（next）数组
	   @complexity: O(n)
	   @param: pattern, 		(RandomAccessIterator)
	           end of pattern,	(RandomAccessIterator) 
	   		   [out] next array	(RandomAccessIterator)
	   @return: pointer to next */
	template<typename StrIter, typename NextIter>
	inline NextIter kmp_next(
		StrIter pattern, 
		StrIter pattern_end, 
		NextIter next)
	{
		next[0] = -1;
		int cur = 0;
		int pat = -1;
		while(pattern + cur != pattern_end)
		{
			if(pat == -1 || pattern[cur] == pattern[pat])
				next[++cur] = ++pat;
			else pat = next[pat];
		}

		return next;
	}

	inline int* kmp_next(const char* pattern, int* next)
	{
		return kmp_next(pattern, pattern + std::strlen(pattern), next);
	}

	/* @brief: KMP 字符串匹配算法
	   @complexity: O(n + m)
	   @param: source, end of source,    (RandomAccessIterator)
	   		   pattern, end of pattern,  (RandomAccessIterator)
			   next array inited by kmp_next
			   matched position recorder (OutputIterator)
			   							 (ForwardIterator)
			   max matched number
	   @return: output 的末尾 */
	template<typename StrIter, 
			 typename NextIter,
			 typename OutputIter, 
			 typename MaxMatchNumType>
	inline OutputIter kmp_search(
		StrIter source, 
		StrIter source_end,
		StrIter pattern, 
		StrIter pattern_end,
		NextIter next, 
		OutputIter output, 
		MaxMatchNumType max_match_num)
	{
		int cur = 0;
		int pat = 0;
		MaxMatchNumType matched = 0;
		while(source + cur != source_end)
		{
			if(pat == -1 || source[cur] == pattern[pat])
			{
				++cur, ++pat;
				if(pattern_end - pattern == pat)
				{
					*output++ = source + (cur-- - pat);
					if(++matched == max_match_num)
						return output;
					pat = next[pat - 1];
				}
			} else {
				pat = next[pat];
			}
		}

		return output;
	}

	/* @brief: KMP 字符串匹配算法
	   @complexity: O(n + m)
	   @param: source, end of source,    (RandomAccessIterator)
	   		   pattern, end of pattern,  (RandomAccessIterator)
			   next array inited by kmp_next
	   @return: 母串第一个匹配的地方，
	 			如果没有这样的地方 source_end 被返回 */
	template<typename StrIter, 
			 typename NextIter>
	inline StrIter kmp_search(
		StrIter source, 
		StrIter source_end,
		StrIter pattern, 
		StrIter pattern_end,
		NextIter next)
	{
		StrIter pos = source_end;
		kmp_search(
			source, source_end, 
			pattern, pattern_end, 
			next, &pos, 1);
		return pos;

	}

	inline const char* kmp_search(
		const char* source, 
		const char* pattern, 
		const int* next)
	{
		return kmp_search(source, source + std::strlen(source), 
			pattern, pattern + std::strlen(pattern), next);
	}
}

#endif
